CODE 146. Max Points on a Line

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/28/2013-11-28-CODE 146 Max Points on a Line/

访问原文「CODE 146. Max Points on a Line」

Given n points
on a 2D plane, find the maximum number of points that lie on the same straight line.

public int maxPoints(Point[] points) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.

	Map<Float, Integer> kmap = new HashMap<Float, Integer>();
	int size = points.length;
	int total = 0;
	int sum_cloumn = 0;

	if (size <= 2) {
		return size;
	}

	for (int i = 0; i < size; i++) {
		sum_cloumn = 0;
		int add = 1;
		kmap.clear();
		for (int j = 0; j < size; j++) {
			if (j == i) {
				continue;
			}

			if (points[i].x == points[j].x && points[i].y == points[j].y) {
				add++;
				continue;
			}

			float k = 0;

			if (points[i].x != points[j].x) {
				k = (float) (points[j].y - points[i].y)
						/ (points[j].x - points[i].x);
				if (kmap.containsKey(k)) {
					kmap.put(k, kmap.get(k) + 1);
				} else {
					kmap.put(k, 1);
				}
			} else {
				sum_cloumn++;
			}
		}
		for (Float f : kmap.keySet()) {
			if (kmap.get(f) > sum_cloumn) {
				sum_cloumn = kmap.get(f);
			}
		}
		sum_cloumn += add;

		if (sum_cloumn > total) {
			total = sum_cloumn;
		}
	}
	return total;
}